The present invention is in the field of analog computation circuits, and in particular relates to the use of the parasitic resistance of field programmable interconnect devices to solve finite difference method problems.
The field programmable interconnect device (FPID) is a special-purpose integrated circuit, consisting of a large number of transistor-based electronic switches. The FPID is generically shown in FIG. 1. Its design normally involves a number of externally available input/output (I/O) terminal contacts, a set of wiring pathways, switches between the pathways (represented as circles at a number of the crossing points), and a control circuit that determines which switches are closed based a prescribed pattern, specified from a configuration port. The FPID permits the flexible and agile interconnection between a number of the device""s input/output terminals, so that normally isolated parts of a networks can be shorted together, or conversely, so that in designs, some of the connected parts of a network can be isolated by opening switches.
In the simplified FIG. 1 representation, each terminal is connected to a row and column in the wiring array, so that xe2x80x9cAxe2x80x9d is actually connected to row A and column A, etc. For n terminals, this results in 2 n wires (n rows and n columns). Though this arrangement results in n2 junctions of rows and columns, only (n2/2xe2x88x92n) switches are required to fully connect the n terminals in any combination. This configuration is sometimes referred to as a fully connected crossbar.
In the unachievable ideal case, the switches represent zero-ohm, zero-length wires when closed and infinite resistance connections when opened. Since most FPIDs are based on silicon MOSFET devices, however, the switches do not achieve the ideal behavior. FIG. 2 illustrates the various representations of the switch in an FPID. FIG. 2a is the simplified symbolic representation. FIG. 2b is the familiar standard symbolic representation. FIGS. 2c and 2d represent the n-channel MOSFET and CMOS (n-channel plus p-channel) transmission gate structures respectively, which closely represent the actual switch structures in FPID devices. FIG. 3 provides a more physically accurate representation of an n-channel MOSFET. FIG. 3b illustrates the formation of an inversion channel between the drain and source, resulting in a conductive path, the situation more closely representing the closure of an FPID switch. The switch actually behaves more like the resistor shown in FIG. 3c, a fact very important to the principle behind the present invention.
Since the switch is a poor switch, the FPID is considered a digital device, for use in switched logic systems. Switch logic systems compensate for the slight signal degradations of transmission gates due to the restorative nature of digital logic systems such as CMOS. For general purpose analog, however, the non-zero resistance of the transmission gate switch (values may range from 50 ohms to 500 ohms, based on the underlying switch design and process technology) results in unwanted signal deterioration and design complexity. Hence, even though it is possible to use FPIDs for analog applications, it is uncommon to use them for these applications due to the normally undesired parasitic resistance.
It is conceivable, however, that the parasitic resistance could be harnessed in particular circuit designs. One such possibility includes the utilization of FPIDs to form certain types of resistive networks, in which the normally parasitic resistance now plays a key role in the operation of that network. One such circuit class is a linear equation solver, for example, based on the finite difference method.
The finite difference method uses a discrete approximation of differential equations to reduce them to a system of algebraic equations. For example, the following is a derivation of the finite difference representations of Laplace""s equation in one-dimension
Define Laplace""s equation:
∇2V=0xe2x80x83xe2x80x83(1) 
In one-dimension, Equation (1) becomes:                                                         ⅆ              2                        ⁢            V                                ⅆ                          x              2                                      =        0                            (        2        )            
The finite forward difference is an approximation of the definition of a derivative:                                                         ⅆ                              V                ⁡                                  (                  x                  )                                                                    ⅆ              x                                ≅                                                    V                ⁡                                  (                                      x                    +                    Δ                                    )                                            -                              V                ⁡                                  (                  x                  )                                                                                    (                                  x                  +                  Δ                                )                            -              x                                      =                                            V              ⁡                              (                                  x                  +                  Δ                                )                                      -                          V              ⁡                              (                x                )                                              Δ                                    (        3        )            
Also, define:                                           ⅆ                          V              ⁡                              (                                  x                  -                  Δ                                )                                                          ⅆ            x                          ≅                                            V              ⁡                              (                x                )                                      -                          V              ⁡                              (                                  x                  -                  Δ                                )                                              Δ                                    (        4        )            
Finite difference representation of higher-level derivatives can be analogously defined:                                                         ⅆ              2                        ⁢                          V              ⁡                              (                x                )                                                          ⅆ                          x              2                                      ≅                                                            ⅆ                                  V                  ⁡                                      (                                          x                      +                      Δ                                        )                                                                              ⅆ                x                                      -                                          ⅆ                                  V                  ⁡                                      (                    x                    )                                                                              ⅆ                x                                              x                                    (        5        )            
As xcex94xe2x86x920, the approximation improves, being identical to the xe2x80x9ctruexe2x80x9d derivative in the limit as xcex94xe2x86x920. Hence,             x      ≈              (                  x          +          Δ                )              ;                  V        ⁡                  (          x          )                    ≈              V        ⁡                  (                      x            +            Δ                    )                      ;                                ⅆ                      V            ⁡                          (              x              )                                                ⅆ          x                    ≈                        ⅆ                      V            ⁡                          (                              x                +                Δ                            )                                                ⅆ          x                      ;                                        ⅆ            2                    ⁢                      V            ⁡                          (              x              )                                                ⅆ                      x            2                              ≈                                    ⅆ            2                    ⁢                      V            ⁡                          (                              x                +                Δ                            )                                                ⅆ                      x            2                                ;  
etc. So, for convenience we develop the finite difference representation of             ⅆ      2        ⁢          V      ⁡              (                  x          -          Δ                )                  ⅆ          x      2      
and recognize it as an approximation of             ⅆ      2        ⁢          V      ⁡              (        x        )                  ⅆ          x      2      
using (3) and (4):                                                                                                               ⅆ                    2                                    ⁢                                      V                    ⁡                                          (                                              x                        -                        Δ                                            )                                                                                        ⅆ                                      x                    2                                                              =                            ⁢                                                                                          ⅆ                                              V                        ⁡                                                  (                          x                          )                                                                                                            ⅆ                      x                                                        -                                                            ⅆ                                              V                        ⁡                                                  (                                                      x                            -                            Δ                                                    )                                                                                                            ⅆ                      x                                                                      x                                                                                        =                            ⁢                                                                                                                  V                        ⁡                                                  (                                                      x                            +                            Δ                                                    )                                                                    -                                              V                        ⁡                                                  (                          x                          )                                                                                      Δ                                    -                                                                                    V                        ⁡                                                  (                          x                          )                                                                    -                                              V                        ⁡                                                  (                                                      x                            -                            Δ                                                    )                                                                                      Δ                                                  Δ                                                                                        =                            ⁢                                                                    V                    ⁡                                          (                                              x                        +                        Δ                                            )                                                        +                                      V                    ⁡                                          (                                              x                        -                        Δ                                            )                                                        -                                      2                    ⁢                                          V                      ⁡                                              (                        x                        )                                                                                                              Δ                  2                                                                                                        ≅                            ⁢                                                                    ⅆ                    2                                    ⁢                                      V                    ⁡                                          (                                              x                        -                        Δ                                            )                                                                                        ⅆ                                      x                    2                                                                                                                          ≅                            ⁢                                                                    ⅆ                    2                                    ⁢                                      V                    ⁡                                          (                      x                      )                                                                                        ⅆ                                      x                    2                                                                                                          (        6        )            
and therefore we can write a finite difference approximation to (1) (using (6)) as:                                                         ∇              2                        ⁢            V                    ≅                                                    V                ⁡                                  (                                      x                    +                    Δ                                    )                                            +                              V                ⁡                                  (                                      x                    -                    Δ                                    )                                            -                              2                ⁢                                  V                  ⁡                                      (                    x                    )                                                                                      Δ              2                                      =                              0            ⇒                                          V                ⁡                                  (                                      x                    +                    Δ                                    )                                            +                              V                ⁡                                  (                                      x                    -                    Δ                                    )                                            -                              2                ⁢                                  V                  ⁡                                      (                    x                    )                                                                                =                                    0              ⇒                                                V                  ⁡                                      (                                          x                      +                      Δ                                        )                                                  +                                  V                  ⁡                                      (                                          x                      -                      Δ                                        )                                                                        =                          2              ⁢                              V                ⁡                                  (                  x                  )                                                                                        xe2x80x83                                          xe2x80x83                ⁢                              V            ⁢                          (              x              )                                =                                    1              2                        ⁢                          (                                                V                  ⁡                                      (                                          x                      +                      Δ                                        )                                                  -                                  V                  ⁡                                      (                                          x                      -                      Δ                                        )                                                              )                                                          (        7        )            
Equation (7) is then the finite difference representation of Laplace""s equation in one-dimension.
To simplify implementation in a discrete system or a computer, the A""s are typically replaced by integral indices, yielding the familiar form of a finite difference equation:                               V          ⁡                      (            x            )                          =                              1            2                    ⁢                      (                                          V                ⁡                                  (                                      x                    +                    i                                    )                                            -                              V                ⁡                                  (                                      x                    -                    i                                    )                                                      )                                              (        8        )            
Extending this analysis to multiple dimensions is straightforward. For two dimensions, Equation (1) becomes:                                           ∇            2                    ⁢                      V            ⁡                          (                              x                ,                y                            )                                      =                                                            ∂                2                            ⁢                              V                ⁡                                  (                                      x                    ,                    y                                    )                                                                    ∂                              x                2                                              +                                                    ∂                2                            ⁢                              V                ⁡                                  (                                      x                    ,                    y                                    )                                                                    ∂                              y                2                                                                        (        9        )            
Through the previous analyses, we can directly write the approximation of Equation (9) as:                                           ∇            2                    ⁢                      V            ⁡                          (                              x                ,                y                            )                                      ≅                ⁢                                                                                                  (                                                                                                                        V                            ⁡                                                          (                                                                                                x                                  +                                  Δ                                                                ,                                y                                                            )                                                                                -                                                      V                            ⁡                                                          (                                                              x                                ,                                y                                                            )                                                                                                      Δ                                            -                                                                                                    V                            ⁡                                                          (                                                              x                                ,                                y                                                            )                                                                                -                                                      V                            ⁡                                                          (                                                                                                x                                  -                                  Δ                                                                ,                                y                                                            )                                                                                                      Δ                                                              )                                    +                                                                                                      (                                                                                                              V                          ⁡                                                      (                                                          x                              ,                                                              y                                +                                Δ                                                                                      )                                                                          -                                                  V                          ⁡                                                      (                                                          x                              ,                              y                                                        )                                                                                              Δ                                        -                                                                                            V                          ⁡                                                      (                                                          x                              ,                              y                                                        )                                                                          -                                                  V                          ⁡                                                      (                                                          x                              ,                                                              y                                -                                Δ                                                                                      )                                                                                              Δ                                                        )                                                              Δ                                        =                ⁢                                                                                                  V                    ⁡                                          (                                                                        x                          +                          Δ                                                ,                        y                                            )                                                        +                                      V                    ⁡                                          (                                                                        x                          -                          Δ                                                ,                        y                                            )                                                        +                                                                                                                          V                    ⁢                                          (                                              x                        ,                                                  y                          +                          Δ                                                                    )                                                        +                                      V                    ⁡                                          (                                              x                        ,                                                  y                          -                          Δ                                                                    )                                                        -                                      4                    ⁢                                          V                      ⁡                                              (                                                  x                          ,                          y                                                )                                                                                                                                      Δ            2                                                  =                ⁢        0            
This results in the two-dimensional finite difference method expression:                               V          ⁡                      (                          x              ,              y                        )                          =                              1            4                    ⁢                      (                                          V                ⁡                                  (                                                            x                      +                      Δ                                        ,                    y                                    )                                            +                              V                ⁡                                  (                                                            x                      -                      Δ                                        ,                    y                                    )                                            +                              V                ⁡                                  (                                      x                    ,                                          y                      +                      Δ                                                        )                                            +                              V                ⁡                                  (                                      x                    ,                                          y                      -                      Δ                                                        )                                                      )                                              (        10        )            
Which can be written in the indexed form as:                               V          ⁡                      (                          x              ,              y                        )                          =                              1            4                    ⁢                      (                                          V                ⁡                                  (                                                            x                      +                      1                                        ,                    y                                    )                                            +                              V                ⁡                                  (                                                            x                      -                      1                                        ,                    y                                    )                                            +                              V                ⁡                                  (                                      x                    ,                                          y                      +                      1                                                        )                                            +                              V                ⁡                                  (                                      x                    ,                                          y                      -                      1                                                        )                                                      )                                              (        11        )            
In particular, it will be shown that it is possible to reduce the solution of Poisson""s equation:
∇2V=xcfx81
over a two-dimensional (2-D) space to an equation at each of many discrete points on a grid formed onto this space:
V(x,y)=1/4*(V(x+dx,y)+V(xxe2x88x92dx,y)+V(x,y+dy)+V(x,ydy)) 
An electrical analog of this discretization can then be realized by using a grid network of resistors. Boundary conditions are simulated by impressing voltages on particular nodes. These sources correspond to Dirichlet boundary conditions. Of course, Poisson""s equation reduces to Laplace""s equation in source free regions:
∇2V=0 
In a preferred embodiment, the invention exploits the parasitic resistances of field programmable interconnect devices in the form of a programmable resistive grid to solve a wide variety of linear partial differential equations. The grid can be programmed to mimic the nodal relationships defined in finite difference method models with voltages impressed on externally accessible pins corresponding to Dirichlet boundary conditions and a means to read out the solutions (voltages) at the grid nodal points. A resistive grid may contain up to hundreds of terminals. Problems requiring even greater nodal points can be solved sequentially using a plurality of resistive grids with the outputs of the first resistive grid component forming the input, boundary conditions of the next resistive grid component. Such an approach has a distinct advantage over custom solvers that are normally higher in performance but fixed in their connection topology.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawing, illustrating by way of example the principles of the invention.